\section{Background}\label{sec:background}


We now formally define cost sensitive temporally expressive~(CSTE)
planning. %We assume a discrete time horizon. 
A \textbf{fact} $f$ is
an atomic proposition that can be either true or false; we use $f_t$
to represent the fact $f$ at time $t$. A \textbf{state} $S$ is a set of 
facts that are true. We use $S_t$ to represent the state at time $t$.
%: $S_t=\{f_t|f~is~ true~ at~ time~ t\}$.

\begin{defn}\em (Cost-sensitive durative action).
A cost-sensitive durative action $o$ is defined by a tuple
$$(\rho,\mu,\pi_{\vdash},\pi_{\leftrightarrow},\pi_{\dashv},\alpha_{\vdash},\alpha_{\dashv}),$$
where $\rho$ and $\mu$
%, both positive constants, 
are the duration and cost of $o$, respectively;
$\pi_{\vdash}, \pi_{\dashv}$ are precondition fact sets that
must be true at the start and at the end of $o$, respectively;
$\pi_{\leftrightarrow}$ is the overall fact sets that must be true over lifetime, respectively; 
and $\alpha_{\vdash},\alpha_{\dashv}$ are the effects
at the start and the end of $o$, respectively.
\end{defn}
 
In this paper, we assume that action durations and costs are integers where $\rho(o) > 0$ and $\mu(o) \geq 0$.
%In the rest of the paper, 
Given a durative action $o$, we use $\pi_{\vdash}$ to represent $\pi_{\vdash}(o)$.
The same abbreviation applies to $\pi_{\leftrightarrow}, \pi_{\dashv}, \alpha_{\vdash}$, and $\alpha_{\dashv}$.
In PDDL2.1, the annotations of precondition and overall facts are:
1) $\pi_{\vdash}$: ``(at start f)", 2) $\pi_{\dashv}$: ``(at end f)", and 3) $\pi_{\leftrightarrow}$: ``(over all f)".
The annotations of effects are:
1) $\alpha_{\vdash}$: ``(at start f)" and 2) $\alpha_{\dashv}$: ``(at end f)".

Given an action $o$ and a sequence of states $S_t,
S_{t+1},...,S_{t+\rho(o)-1}$, $o$ is \emph{\textbf{applicable}} at
time $t$ (denoted as $o_t$) if the following conditions are satisfied: a) $\forall f
\in \pi_{\vdash}, f_t\in S_t$; b) $\forall f \in \pi_{\dashv},
f_{t+\rho(o)-1}\in S_{t+\rho(o)-1}$; and c) $\forall f\in
\pi_{\leftrightarrow}, t'\in (t,t+\rho(o)-1), f_{t'}\in S_{t'}$.


Action $o$'s execution at time $t$ will affects states $S_{t+1}$ and $S_{t+\rho(o)}$.
%will be changed according to $\alpha_{\vdash}$  and $S_{t+\rho(o)}$ changed according to $\alpha_{\dashv}$.
%Qiang 3.15
States $S_{t+1}$ and $S_{t+\rho(o)}$ {\bf \em satisfy} $o_t$'s effects if: 1) for each add-effect $f\in \alpha_{\vdash}$, $f_{t+1} \in S_{t+1}$,
2) for each delete-effect $(not~f) \in \alpha_{\vdash}$, $f_{t+1}\notin S_{t+1}$, 3) for each add-effect $f \in \alpha_{\dashv}$, $f_{t+\rho(o)} \in S_{t+\rho(o)}$, and 4) for each delete-effect $(not~f) \in \alpha_{\dashv}$, $f_{t+\rho(o)} \notin S_{t+\rho(o)}$.

\nop{
$\alpha \in\{\alpha_{\vdash}, \alpha_{\dashv}\}$
if and only if: a) for each add-effect $f \in \alpha$, $f_t \in S_t$; and b) for
each delete-effect $(not~f)\in \alpha$, $f_t \notin S_t$.
}

\nop{ Assuming $o$ is executed at time $t$, which implies that $o$
ends at time $t+\rho-1$, we need all the conditions to be satisfied
as follows: a) $\forall f \in \pi_{\vdash}, f_t$ is true, b)
$\forall f \in \pi_{\dashv}, f_{t+\rho-1}$ is true, and c) $\forall
f\in \pi_{\leftrightarrow}, t'\in (t,t+\rho-1), f_{t'}$ is true. Let
us denote the state at time $t$ and $t+\rho-1$ to be $s_1$ and
$s_2$. After $o$ is executed, $s_1$ and $s_2$ will become $s_1\cup
\alpha_{\vdash}$ and $s_2\cup \alpha_{\dashv}$, respectively.}


\begin{defn} \em (Cost-sensitive temporal (CST) planning).
A cost-sensitive temporal planning problem $\Pi$ is defined as
a tuple $(I,F,O,G)$, where $I$ is the initial state, $F$ is a set
of facts, $O$ is a set of cost-sensitive durative actions, and $G$ is
a set of goal facts.
\end{defn}

This formulation of CST planning is a subset of PDDL2.1~\cite{Fox03pddl2.1}.

%For simplicity, we assume each action $o\in O$ to be durative and grounded.


\begin{defn}\em (Solution plan).\label{def:plan}
Given a CST planning problem $\Pi=(I,F,O,G)$, a plan
$P=(p_0,p_1,\dots,p_{n-1})$ is a sequence of action sets, where each action set
$p_t\subseteq O$ indicates the actions executed at time $t$.  $P$ is
a solution plan if there exists a state sequence $S_0, S_1,...,S_n$ satisfying: 
a) $S_0=I$;
b) for each action $o_t\in p_t$,  $o_t$ is applicable at time $t$, and $S_{t+1},~S_{t+\rho(o)}$ satisfy $o_t$'s effects;
c) for all $f\in G$, $f_n \in S_n$.
\end{defn}

Given a plan $P=(p_0,p_1,\dots,p_{n-1})$, there are two metrics that are of our interests:
\begin{enumerate}
\item \textbf{Makespan}, defined as the duration of the
plan:
$$ \max_{t=0, \cdots, n-1}\{\max_{o\in p_t}\{t+\rho(o)-1\}\};$$
\item \textbf{Total action costs}, defined as the total costs of the selected actions (multiple appearances are counted multiple times):
$$\sum_{t=0}^{n-1}\sum_{o\in p_t}{\mu(o)}.$$
\end{enumerate}

\begin{defn}\em (Required concurrency).
A CST planning problem $\Pi$ has required concurrency if it has at
least one solution plan and every solution plan of $\Pi$ has
concurrently executed actions.
\end{defn}


\begin{defn}{\em (Temporal dependency)} \label{def:depc}
Given two durative actions $o$ and $o'$, we define that $o$
temporally depends on $o'$ when one of the following conditions
holds:
\begin{enumerate}
\item $\exists f \in \pi_{\vdash}(o)$, such that $f\in \alpha_{\vdash}(o')$ and
$\neg f\in \alpha_{\dashv}(o')$;

\item $\exists \neg f \in \pi_{\vdash}(o)$, such that $\neg f\in \alpha_{\vdash}(o')$ and
$f\in \alpha_{\dashv}(o')$.

\end{enumerate}
\end{defn}

Two factors can lead to concurrencies in a temporally expressive
problem. One is the required concurrent interaction (i.e.,
concurrent execution) among actions, and the other is enforced deadlines~\cite{Coles08}.  

%Note that a temporal dependency among
%actions is just a sufficient condition for required concurrencies. A
%problem is temporally expressive only when there exists no action
%that can achieve the goals if the temporal dependency is ignored.

\nop{
In our study, we adopt the concept of required concurrency, which was introduced in~\cite{Cushing07:ICAPS}. A temporal problem has required concurrency when, in any solution, there exist two actions $o_1$ and $o_2$ such that:
1) $o_1$ has two effects (at start $f$) and (at end (not $f$)) (which means $f$ is an interval add-effect), and 2) $o_2$ has a precondition (at start $f$).
These two conditions require $o_1$ and $o_2$ to be executed concurrently.
}

\begin{defn} \em (Cost-sensitive temporally expressive (CSTE) planning).
A CSTE planning problem is a CST planning problem with required concurrency.
\end{defn}

